package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by 林剑 on 2016/10/8.
 */
public class leetcode47 {
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        ArrayList<Integer> item = new ArrayList<Integer>();

        if(num == null || num.length == 0)
            return res;
        boolean [] visited = new boolean[num.length];
        Arrays.sort(num);
        permutationhelper(res, num, item, visited);
        return res;
    }

    public void permutationhelper(List<List<Integer>> res, int[] num, ArrayList<Integer> item, boolean[] visited){
        if(item.size() == num.length){
            res.add(new ArrayList<Integer>(item));
            return;
        }

        for(int i = 0; i < num.length; i++){
            if(i > 0 && num[i] == num[i-1] && !visited[i - 1])
                continue;
            if(!visited[i]){
                item.add(num[i]);
                visited[i] = true;
                permutationhelper(res, num, item, visited);
                visited[i] = false;
                item.remove(item.size()-1);
            }
        }
    }
    public static void main(String[] args) {
        leetcode47 leetcode47 = new leetcode47();
        int[] a = {1,2,3};
        System.out.println(leetcode47.permuteUnique(a));
    }
}
